---
title: "路径计数"
created: 2025-11-28
tags:
  - 算法
---

# 路径计数

## 题目 [路径计数](https://www.lanqiao.cn/paper/3845/problem/817/)

![[image-b40b6d0f.png]]

## 思路分析

路径数 dfs吗

起点0,0 终点0,0

写的时候发现一个问题

0,0点一开始被标记了已走过 导致到不了终点 可是如果不标记走过的话 就可能一直走回头路

需要一种解决措施 使得0,0位置在走的时候不会被重复走 且最后还能回到0,0处 ？

或者换个思路 从1,0处和0,1处作为起点 找它们到终点0,0的路径数 最后减去2（1，0直接到0,0 相当于0,0->1,0->0,1实际非法
0,1直接到0,0同理） 或者直接找1,0和0,1为起点 到0,0的 路径长度大于2的所有方案数

最后注意 因为是从0,1 和 1,0开始的 默认是已经从0,0走到了这两个位置 所以step一开始为1

很多细节这题 又是填空 一不小心就会错

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=10;
int cnt=0;
bool st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
	return x>=0 && x<=4 && y>=0 && y<=4 && !st[x][y];
}
void dfs(int x,int y,int step){
	if(step>12)	return;
	if(x==0 && y==0 && step > 2){
		cnt++;
		return;
	}

	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(isVaild(nx,ny)){
			st[nx][ny]=true;
			dfs(nx,ny,step+1);
			st[nx][ny]=false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	st[1][0]=true;
	dfs(1,0,1);
	st[1][0]=false;
	st[0][1]=true;
	dfs(0,1,1);
	st[0][1]=false;
	cout<<cnt;
	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[求值|求值]] 🏠 [[00-冲刺国赛]] ➡️ [[最优包含|最优包含]]